2.1 Terminologi

Algoritma DBSCAN memerlukan dua parameter input sebelum melakukan proses clustering yaitu epsilon dan minPts. Epsilon merupakan jarak maksimal antara dua amatan dalam satu cluster yang diizinkan, dan minPts adalah banyaknya data minimal dalam jarak epsilon agar terbentuk suatu cluster. Metode jarak yang digunakan dalam Algoritma DBSCAN adalah jarak Euclidian. Sepasang amatan dikatakan bertetangga apabila jarak antara dua amatan tersebut kurang dari sama dengan nilai epsilon. Selain epsilon dan MinPts ada beberapa terminologi lain dalam metode DBSCAN yaitu :

• directly density-reachable : observasi q berhubungan langsung dengan p, jika p adalah core point dan q merupakan tetangga dari p dalam jangkauan epsilon.
  
• density-reachable : observasi q dan x dalam satu cluster namun x bukan tetangga dari q dalam jangkauan epsilon.
  
• core point : core point merupakan observasi yang memiliki jumlah tetangga lebih dari sama dengan dari MinPts pada jangkauan Eps.
  
• border point : border point memiliki tetangga lebih sedikit dari Minpts namun ia merupakan tetangga dari core point.
  
• outlier/noise point : observasi yang bukan border points atau core points.

2.2 Cara Kerja DBSCAN

secara sederhana cara kerja DBSCAN adalah sebagai berikut :
1. tentukan nilai Minpts dan epsilon (eps) yang akan digunakan.
2. Pilih data awal “p” secara acak.
3. Hitung jarak antara data “p” terhadap semua data menggunakan Euclidian distance.
4. Ambil semua amatan yang density-reachable dengan amatan “p”.
5. Jika amatan yang memenuhi nilai epsilon lebih dari jumlah minimal amatan dalam satu gerombol maka amatan “p” dikategorikan sebagai core points dan gerombol terbentuk.
6. Jika amatan “p” adalah border points dan tidak ada amatan yang density-reachable dengan amatan “p”, maka lanjutkan pada amatan lainnya.
7. Ulangi langkah 3 sampai 6 hingga semua amatan diproses.

3.1 Data Eksplorasi

untuk menggunakan metode DBSCAN pada R anda harus menginstall packges dbscan terlebih dahulu. Data yang digunakan adalah data multishape dari packages factoextra, pada data ini terdapat 3 variabel yaitu x, y, dan shape. untuk proses pembuatan cluster, variabel yang akan digunakan hanya x dan y.

data("multishapes")
multishapes <- multishapes[,1:2]
head(multishapes)

##            x          y
## 1 -0.8037393 -0.8530526
## 2  0.8528507  0.3676184
## 3  0.9271795 -0.2749024
## 4 -0.7526261 -0.5115652
## 5  0.7068462  0.8106792
## 6  1.0346985  0.3946550

Secara visual data multishape dapat dilihat seperti plot dibawah. Pada plot tersebut terlihat bahwa kerapatan antar data membentuk beberapa bentuk seperti lingkaran dan persegi panjang.

ggplot(data = multishapes, aes(x = x, y = y)) +
  geom_point(col = "firebrick4") +
  theme_pander()

3.2 Clustering

Tahap awal sebelum melakukan clustering adalah memilih nilai nilai minpts dan epsilon (eps). Untuk memilih nilai minpts dan eps yang tepat bisa menggunakan function kNNdistplot dari packages dbscan. Ide utama dari fungsi ini adalah menghitung jarak rata2 untuk setiap data ke k tetangga terdekatnya (nearest neighbors). Nilai dari K ditentukan oleh user yang nantinya akan digunakan sebagai minPts pada proses clustering. Selanjutnya rata rata jarak tersebut diplot secara ascending untuk mendapatkan “knee” yang menunjukkan nilai optimal dari eps berdasarkan K yang ditentukan.

kNNdistplot(multishapes, k = 4)
abline(h = 0.15, col = "red", lty = 2)

Berdasarkan plot diatas dengan menggunakan K = 4 didapat jarak yang optimal yaitu sekitar 0.15. Nilai 0.15 didapat dari posisi “knee” yang terbentuk pada plot. dengan menggunakan hasil plot diatas maka nilai Eps yang digunakan pada proses clustering adalah 0.15 dengan minPts 4. Tahap selanjutnya adalah pembuatan cluster menggunakan function dbscan dengan parameter yang sudah didapat.

db_clust <- dbscan(multishapes, eps = 0.15, minPts = 4)
db_clust

## DBSCAN clustering for 1100 objects.
## Parameters: eps = 0.15, minPts = 4
## The clustering contains 5 cluster(s) and 29 noise points.
## 
##   0   1   2   3   4   5 
##  29 411 405 105  99  51 
## 
## Available fields: cluster, eps, minPts

Hasil clustering dari data multishape dengan 1100 observasi adalah 5 cluster dan sebanyak 29 data diidentifikasi sebagai noise. Cluster 1 merupakan cluster dengan anggota cluster terbanyak sedangkan cluster 5 merupakan cluster dengan anggota cluster paling sedikit. Hasil cluster yang sudah dibentuk dapat dilakukan visualisasi agar terlihat pola dari cluster yang didapat.

multishapes <- multishapes %>% 
  mutate(clust = db_clust$cluster, 
         clust = ifelse(clust==0,"Noise",clust)) 

ggplot(data =multishapes, aes(x = x, y = y)) +
geom_point(aes(col = as.factor(clust))) +
theme_pander() +
labs(col = "Cluster")

Dari hasil visualisasi diatas bisa dilihat bahwa cluster yang dihasilkan dbscan dapat mengelompokkan data sehingga bisa menangkap beberapa bentuk dari data. Noise yang terdeteksi pada data terlihat menyebar, hal ini dikarenakan data noise tidak berhasil ditangkap eps yang ditentukan.

DBSCAN merupakan metode clustering yang sangat sensitif terhadap perubahan parameter. Perbedaan kecil pada parameter yang ada (minPts, Eps) dapat menghasilkan cluster yang berbeda. Sebagai contoh pada data multishapes yang sebelumnya digunakan apabila nilai eps diubah yang awalnya 0.15 menjadi 0.2 akan menghasilkan cluster yang berbeda

db_clust <- dbscan(multishapes[,1:2], eps = 0.2, minPts = 4)
db_clust

## DBSCAN clustering for 1100 objects.
## Parameters: eps = 0.2, minPts = 4
## The clustering contains 4 cluster(s) and 20 noise points.
## 
##   0   1   2   3   4 
##  20 820 106 102  52 
## 
## Available fields: cluster, eps, minPts

dengan mengubah parameter eps yang semula 0.15 menjadi 0.2 maka hasil cluster yang terbentuk menjadi 4 dan noise yang dihasilkan menjadi semakin berkurang yaitu 20. Bila diamati lebih detail lagi cluster 1 mengalami penambahan anggota cluster secara signifikan, yang semula 411 menjadi 820. Pola cluster yang sudah dibuat dapat divisualisasikan agar dapat melihat perbedaan dengan proses clustering sebelumnya.

multishapes <- multishapes %>% 
  mutate(clust = db_clust$cluster, 
         clust = ifelse(clust==0,"Noise",clust)) 

ggplot(data =multishapes, aes(x = x, y = y)) +
geom_point(aes(col = as.factor(clust))) +
theme_pander() +
labs(col = "Cluster")

Dari hasil visualisasi diatas bisa dilihat bahwa cluster 1 yang baru menggabungkan cluster 1 dan 2 pada proses cluster sebelumnya, serta noise yang awalnya berada disekitar cluster 1 menjadi anggota cluster 1.